package acwing.lq.递归and递推;

import java.util.Scanner;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/11/10
 */
public class 递归实现指数型枚举 {


    static int[] state; // 状态 1表示没选 2表示选中
    static int n;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        n = s.nextInt();

        state = new int[n + 1];
        dfs(0);

    }

    private static void dfs(int i) {
        if (i == n) {
            for (i = 0; i <= n; i++) {
                if (state[i] == 1) {
                    System.out.print(i + 1 + " ");
                }
            }
            System.out.println();
            return;
        }
        state[i] = 1;
        dfs(i + 1);
        state[i] = 0;

        state[i] = 2;
        dfs(i + 1);
        state[i] = 0;
    }
}
